package com.erbao.datastructurearithmetic.base;

import com.erbao.datastructurearithmetic.tyro.Class1;

/**
 * @author CaoBaoYin
 * @since 2021/12/5 17:34
 */
public class Class03 {

    /**
     * 快速排序
     * @param arr 未排序数组
     */
    public void quickSort(int[] arr) {
        if (arr == null || arr.length < 2) return ;

        processQuickSort (arr, 0, arr.length-1);
    }

    private void processQuickSort(int[] arr, int l, int r) {
        if (l >= r) return;

        int i = l + (int) (Math.random() * (r - l + 1));
        Class1.swap(arr, i, r);

        int[] partition = partition(arr, l, r);
        processQuickSort(arr, l, partition[0]);
        processQuickSort(arr, partition[1], r);
    }

    private int[] partition(int[] arr, int l, int r) {
        if (l >= r) return new int[]{-1, -1};

        /* 边界都在需要划分的数组之外 */
        int leftCursor = l-1;//小于区域边界
        int rightCursor = r;//大于区域边界
        int num = arr[r];// 标杆值

        int index = l;
        while (index < rightCursor) {
            if (arr[index] < num) {
                Class1.swap(arr, ++leftCursor, index++);
            } else if (arr[index] == num) {
                index++;
            } else {
                Class1.swap(arr, index, --rightCursor);
            }
        }

        // 将大于区域边界的值和标杆值交换，此时大于区域边界应该+1
        Class1.swap(arr, rightCursor++, r);
        // 返回边界
        return new int[]{leftCursor, rightCursor};
    }

    /**
     * 归并排序
     * @param arr 未排序数组
     */
    public void mergeSort (int[] arr) {
        if (arr == null || arr.length < 2) return ;

        processMergeSort(arr, 0, arr.length-1);
    }

    /**
     * 数组小和
     * @param arr 数组,数组的值要大于0。数组为空，或者不产生小和时就可以规定返回结果是0
     * @return 小和
     */
    public int smallSum (int[] arr){
        // 规定：空或只有一个元素 直接返回0
        if (arr == null || arr.length < 2) return 0;

        return processSmallSum (arr, 0, arr.length-1);
    }

    /**
     * 数组小和
     * @param arr 数组,数组的值要大于0。数组为空，或者不产生小和时就可以规定返回结果是0
     * @return 小和
     */
    public int smallSumV2 (int[] arr){
        if (arr == null || arr.length < 2) return 0;

        int res = 0;
        for (int i = 0; i < arr.length; i++) {
            for (int j = 0; j < i; j++) {
                if (arr[j] < arr[i]) res += arr[j];
            }
        }

        return res;
    }

    private int processSmallSum(int[] arr, int l, int r) {
        if (l == r) return 0;

        int mid = l + ((r - l) >> 1);

        return processSmallSum(arr, l, mid)
                + processSmallSum(arr, mid+1, r)
                + mergeSmallSum(arr, l, mid, r);// merge这一步产生了小和：本质是比较时可能产生了小和
    }

    private int mergeSmallSum(int[] arr, int l, int mid, int r) {
        int leftCursor = l;
        int rightCursor = mid+1;

        int[] temp = new int[r-l+1];
        int tempIndex = 0;

        int res = 0;
        // 左右两部分合成一部分，只要有一部分合并完就跳出
        while (leftCursor <= mid && rightCursor<=r) {
            if (arr[leftCursor] < arr[rightCursor]) {
                res += arr[leftCursor] * (r - rightCursor + 1);
                temp[tempIndex++] = arr[leftCursor++];
            } else if (arr[leftCursor] > arr[rightCursor]) {
                temp[tempIndex++] = arr[rightCursor++];
            } else {
                /* 相等的情况，右边的值合并，左边的值还需要下次比较右边的值判断是否有小和产生 */
                // temp[tempIndex++] = arr[leftCursor++];
                temp[tempIndex++] = arr[rightCursor++];
            }
        }

        // 剩余左部分未合并完
        if (leftCursor <= mid) {
            System.arraycopy(arr, leftCursor, temp, tempIndex, mid-leftCursor+1);
        }

        // 剩余左部分未合并完
        if (rightCursor <= r) {
            System.arraycopy(arr, rightCursor, temp, tempIndex, r-rightCursor+1);
        }

        System.arraycopy(temp, 0, arr, l, r-l+1);
        return res;
    }

    private void processMergeSort(int[] arr, int l, int r) {
        if (r == l) return ;

        int mid = l + ((r - l) >> 1);

        processMergeSort(arr, l, mid);
        processMergeSort(arr, mid+1, r);

        merge(arr, l, mid, r);
    }

    private void merge(int[] arr, int l, int mid, int r) {

        int leftCursor = l;
        int rightCursor = mid+1;

        int[] temp = new int[r-l+1];
        int tempIndex = 0;

        // 左右两部分合成一部分，只要有一部分合并完就跳出
        while (leftCursor <= mid && rightCursor<=r) {
            if (arr[leftCursor] < arr[rightCursor]) {
                temp[tempIndex++] = arr[leftCursor++];
            } else if (arr[leftCursor] > arr[rightCursor]) {
                temp[tempIndex++] = arr[rightCursor++];
            } else {
                temp[tempIndex++] = arr[leftCursor++];
                temp[tempIndex++] = arr[rightCursor++];
            }
        }

        // 剩余左部分未合并完
        if (leftCursor <= mid) {
            System.arraycopy(arr, leftCursor, temp, tempIndex, mid-leftCursor+1);
        }

        // 剩余左部分未合并完
        if (rightCursor <= r) {
            System.arraycopy(arr, rightCursor, temp, tempIndex, r-rightCursor+1);
        }

        System.arraycopy(temp, 0, arr, l, r-l+1);

    }



}
